﻿#include<stdio.h>

void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

void QuickSort(int* arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

;	int index = begin + 1;
	int prev = begin;
	while (index <= end)
	{
		if (arr[index] < arr[begin] && prev + 1 != index)
		{
			Swap(&arr[prev], &arr[index++]);
		}
		else
		{
			index++;
		}
	}
	Swap(&arr[prev], &arr[begin]);

	QuickSort(arr, begin, prev - 1);
	QuickSort(arr, prev + 1, end);
}

int main()
{
	int arr1[5] = { 1,2,3,4,5 };
	int arr2[6] = { 5,4,3,2,1,0 };
	int arr3[5] = { 1,1,2,1,1 };

	//快速排序
	QuickSort(arr1, 0, 4);
	QuickSort(arr2, 0, 5);
	QuickSort(arr3, 0, 4);

	for (int i = 0; i < 5; i++)
	{
		printf("%d ", arr1[i]);
	}
	printf("\n");
	for (int i = 0; i < 6; i++)
	{
		printf("%d ", arr2[i]);
	}
	printf("\n");
	for (int i = 0; i < 5; i++)
	{
		printf("%d ", arr3[i]);
	}
	printf("\n");
	return 0;
}